public class Test {
    /*
    复习：
    题目 1：
     */
    //最长公共前缀
    //方法一 ：纵向扫描
    public String longestCommonPrefix1(String[] strs) {
        if(strs.length == 0 || strs == null){
            return "";
        }
        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                if(i == strs[j].length() || strs[j].charAt(i) != ch){
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    //方法2：
    //横向扫描：
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        }
        String pre = strs[0];
        for (int i = 1; i < strs.length; i++) {
            pre = commonPrefix(pre, strs[i]);
            if(pre.length() == 0){
                break;
            }
        }
        return  pre;

    }
    private String commonPrefix(String str1, String str2){
        int minlength = Math.min(str1.length(), str2.length());
        int index = 0;
        while(index < minlength && str1.charAt(index) == str2.charAt(index)){
            index++;
        }
        return str1.substring(0, index);
    }

    /*
    题目 2：汉明距离
     */
    //方法1：内置函数
    public int hammingDistance1(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

    //方法2 : 右移 按位与：相同为1 ，才为 1
    public int hammingDistance2(int x, int y) {
        int z = x ^ y;
        int count = 0;
        while(z != 0){
            count += z & 1;
            z >>= 1;
        }
        return count;
    }

    //方法3 ：x & (x - 1) 会删掉 x 二进制位中，最右侧的 0
    public int hammingDistance3(int x, int y) {
        int z = x ^ y;
        int count = 0;
        while(z > 0){
            count++;
            z &= z - 1;
        }
        return count;
    }

    /*
    新题目：
    题目 1：搜索插入位置
     */
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引
    // 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    //请必须使用时间复杂度为 O(log n) 的算法。
    //二分查找：
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        //为了兼容 不存在元素的查找，不能先返回 mid
        //最后一次的循环，一定是 left == right == mid
        //那么，left 的左边，一定全是小于 target 的值
        //right 的右边，一定是大于等于 target 的值
        //如果 target 存在，那么一定在 right + 1 下标的位置！
        //如果 target 不存在
        //那么 nums[mid] > target, right = mid - 1, 退出循环，返回 left
        //如果 nums[mid] < target, left = mid + 1, 退出循环，返回 left
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] < target ){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
    //神奇的不得了！

}
